package com.mzy.linear_struct.ks;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: mizy3
 * @Date: 2024/08/11/下午5:04
 * @Description:
 */
public class Pro42接雨水 {
    public int trap(int[] height) {

        Deque<Integer> stack = new LinkedList<>();

        int ans = 0;
        stack.push(0);
        for (int i = 1; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                Integer mid = stack.pop();
                if (!stack.isEmpty()) {
                    Integer left = stack.peek();
                    int h = Math.min(height[left], height[i]) - height[mid];
                    int w = i - left - 1;
                    int hold = h * w;
                    ans += hold > 0 ? hold : 0;
                }
            }
            stack.push(i);
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Pro42接雨水().trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }
}
